Everything about Lookup Table totally explained
In
computer science, a
lookup table is a
data structure, usually an
array or
associative array, used to replace a runtime computation with a simpler array indexing operation. The speed gain can be significant, since retrieving a value from memory is often faster than undergoing an expensive computation.
A classic example is a
trigonometry calculation for example calculating the
sine of a value every time. Such operation can substantially slow some applications. To avoid this, the application can take a few seconds when it first starts to precalculate the sine of a number of values, for example for each whole number of degrees. Later, when the program wants the sine of a value, it uses the lookup table to retrieve the sine of a nearby value from a memory address instead of calculating it using a mathematical formula. Lookup tables are also used by mathematics co-processors; an error in a lookup table was responsible for Intel's infamous
floating-point divide bug.
Before the advent of computers, similar tables were used by people to speed up hand calculations. Particularly prevalent were tables of values for trigonometry, logarithms, and statistical density functions.
Functions of a single variable (such as sine and cosine) may be implemented by a simple array - functions involving two or more variables require multidimensional array indexing techniques. Hence, one might replace a function to calculate
xy for a limited range of x and y values with a two-dimensional array
power[x][y]. Functions that have more than one result may be implemented with lookup tables that are arrays of structures.
There are intermediate solutions that use tables in combination with a small amount of computation, often using
interpolation. This allows better accuracy for values falling between two precomputed values. This requires slightly more time but can greatly enhance accuracy in applications that require it. Depending on the values being precomputed, this technique can also be used to shrink the lookup table size while retaining about the same accuracy.
In
image processing, lookup tables are often called
LUTs and give an output value for each of a range of index values. One common LUT, called the
colormap or
palette, is used to determine the colors and intensity values with which a particular image will be displayed.
Windowing in
computed tomography refers to a related concept.
It's important to note that, while often effective, lookup tables can result in a severe penalty if the computation it replaces is relatively simple, not only because retrieving the result from memory may require more time, but also because it may increase memory requirements and
pollute the cache. If the table is large, each table access will almost certainly cause a
cache miss. This is increasingly becoming an issue as processors outrace memory. A similar issue appears in
rematerialization, a
compiler optimization. In some environments, such as the
Java programming language, table lookups can be even more expensive due to mandatory bounds-checking involving an additional comparison and branch for each lookup.
There are two fundamental limitations on when it's possible to construct a lookup table for a problem. One is the amount of memory that's available: one can't construct a lookup table larger than the space available for the table, although it's possible to construct disk-based lookup tables at the expense of lookup time. The other restriction is the time required to compute the table values in the first instance — although this usually needs to be done only once, if it takes a prohibitively long time, it may make the use of a lookup table an inappropriate solution.
Examples
Computing sines
Most computers, which only perform basic arithmetic operations, can't directly calculate the
sine of a given value. Instead, they use the
CORDIC algorithm or a complex formula such as the following
Taylor series to compute the value of sine to a high degree of precision:
» 
